7329. Строительство

По окончанию строительства сельского домика у Степана осталось n деревянных досок с длинами l₁, ..., l_n. Он решил построить мостик для ловли рыбы из этих досок.

Степан полагает, что чем длиннее будет мостик, тем больше рыбы он наловит!

Более того, Степан как и все рыбаки, очень суеверен и доверяет приметам. Одна из них состоит в том, что мостик следует строить только из целых досок (доски можно разрезать, но не присоединять). Степан хочет знать, какую максимальную длину d мостика он сможет получить, если тот должен состоять в точности из m досок.

Вход. Целые числа n, m, l_i (1 ≤ n ≤ 10000, 1 ≤ m, l_i ≤ 2 * 10⁹) – количество доступных досок, количество досок, из скольких должен состоять мостик и длины имеющихся в наличии досок.

Выход. Вывести одно целое число d – максимальную возможную длину мостика или 0 (ноль).

Пример входа	Пример выхода
4 6 16 12 20 10	8

РЕШЕНИЕ

бинарный поиск

Анализ алгоритма

Будем искать длину мостика d бинарным поиском. Изначально пусть d Î [Left; Right] = [0; INF]. Рассмотрим следующую подзадачу: можно ли составить требуемый мостик длины в точности Mid = (Left + Right) / 2 ? Для этого посмотрим, сколько всего досок длины Mid можно получить. Из доски длины l_i можно получить таких досок. Путем разрезания можно получить

досок длины Mid. Если суммарно можно получить m досок, то устанавливаем Left = Mid + 1. Иначе положим Right = Mid. Ответом на задачу будет значение Left – 1.

Пример

В заданном примере имеются 4 доски. Необходимо построить мостик шириной в 6 досок.

Если длину мостика взять равной 8, то имеющиеся доски можно разрезать следующим образом, получив 16 / 8 + 12 / 8 + 20 / 8 + 10 / 8 = 6 досок длины 8.

Если длину мостика взять равной 9, то досок длины 9 можно получить только 16 / 9 + 12 / 9 + 20 / 9 + 10 / 9 = 5, что меньше требуемых 6.

Реализация алгоритма

Определим константы. Длины имеющихся в наличии досок l_i храним в массиве a.

#define INF 2000000010

#define MAX 1000009

long long a[MAX];

Функция cnt возвращает количество досок, которое можно вырезать из имеющихся, длины которых будут равны в точности Mid. Это значение равно сумме .

long long cnt(long long Mid)

{

if (Mid == 0) return INF;

long long res = 0;

for(i = 0; i < n; i++)

res += a[i] / Mid;

return res;

}

Основная часть программы. Читаем входные данные.

scanf("%d %d",&n,&m);

for(i = 0; i < n; i++)

scanf("%d",&a[i]);

Устанавливаем границы значения d Î [Left; Right] = [0; INF] и запускаем бинарный поиск.

Left = 0;

Right = INF;

while (Left < Right)

{

Mid = (Left + Right) / 2;

Значение cnt(Mid) равно количеству досок, которое можно вырезать из имеющихся при условии что их длины будут равны Mid. Если это количество меньше требуемого значения m, то длину мостика следует уменьшить, положив Right = Mid. Иначе передвигаем левый конец Left.

if (cnt(Mid) < m) Right = Mid;

else Left = Mid + 1;

}

Выводим ответ.

printf("%lld\n",Left - 1);